#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h>
#include <math.h>
#define N 2 
void sys_err(char* str){
	perror(str);
}

void partition(int* pArray,int lef,int rig,int* key,int* key_index){
	int i = lef,j=rig;//i,j表示当前需要分割区域的下标，所以i=lef,j=rig
	while(i!= j){//key的定位
		for (;pArray[j]>*key && j>i;j--);//有分号
		pArray[i] = pArray[j];
		for (;pArray[i]<= *key && i<j;i++);
		pArray[j] = pArray[i];
		pArray[(*key_index)=i]=*key;
	}
}

void quickSort(int* pArray,int lef,int rig){
	if (lef<rig){//递归条件，lef小于rig
	int key = pArray[lef],key_index=lef;//这里之所以定义在这里，是因为会存在越界访问，虽然代码逻辑不会对空间进行操作，但是leetcode对于数组很严格
		partition(pArray,lef,rig,&key,&key_index);
		quickSort(pArray,lef,key_index-1);
		quickSort(pArray,key_index+1,rig);
	}
}

int* sortedSquares(int* nums, const int numsSize, int* returnSize){
	int* retArray = malloc(numsSize*4);
	*returnSize = numsSize;
	for (int i = 0;i<numsSize;i++){
		retArray[i] = nums[i]*nums[i];
	}*returnSize = numsSize;
	quickSort(retArray,0,numsSize-1);//0就是左，numsSize-1就是右边
	return retArray;
}

int main(int argc,char* argv[]){
	int arr[N] = {-5,1},returnSize;int* pretArray;
	int numsSize = sizeof(arr)/sizeof(int);
	returnSize = numsSize;
	pretArray = sortedSquares(arr,numsSize,&returnSize);
	for (int i = 0;i<returnSize;i++)
		printf("%d ",pretArray[i]);
}
